#define _CRT_SECURE_NO_WARNINGS
//
//#include <iostream>
//#include <string>
//#include <vector>
//#include <list>
//#include <algorithm>
//using namespace std;
//
//void test1()
//{
//	list<int> lt;
//	lt.push_back(10);
//	lt.push_back(2);
//	lt.push_back(5);
//	lt.push_back(6);
//	lt.push_back(1);
//	lt.push_back(7);
//
//	for (auto e : lt) cout << e << ' ';
//	cout << endl;
//
//	lt.sort();
//
//	for (auto e : lt) cout << e << ' ';
//	cout << endl;
//
//	lt.remove(5);
//
//	for (auto e : lt) cout << e << ' ';
//	cout << endl;
//
//	string a("dnaiwdmkefhcgz");
//
//	for (auto e : a) cout << e << ' ';
//	cout << endl;
//
//	sort(a.begin(), a.end());
//
//	for (auto e : a) cout << e << ' ';
//	cout << endl;
//
//	vector<int> v;
//	v.push_back(7);
//	v.push_back(2);
//	v.push_back(1);
//	v.push_back(4);
//	v.push_back(9);
//	v.push_back(3);
//	v.push_back(5);
//	v.push_back(8);
//
//	for (auto e : v) cout << e << ' ';
//	cout << endl;
//
//	sort(v.begin(), v.end());
//
//	for (auto e : v) cout << e << ' ';
//	cout << endl;
//
//	list<int> lt2;
//	lt2.push_back(10);
//	lt2.push_back(20);
//	lt2.push_back(30);
//
//	list<int>::iterator itm = find(lt.begin(), lt.end(), 6);
//
//	lt.splice(itm, lt2);
//
//	for (auto e : lt) cout << e << ' ';
//	cout << endl;
//}
//
//void test2()
//{
//
//}
//
//int main()
//{
//	//test1();
//	test2();
//
//	return 0;
//}

//
//#include <iostream>
//#include <string.h>
//using namespace std;
//
//const int N = 100003;
//int h[N], ne[N], e[N], idx, n;
//
//void insert(int x)
//{
//    int t = (x % N + N) % N;
//    e[idx] = x;
//    ne[idx] = h[t];
//    h[t] = idx++;
//}
//
//bool query(int x)
//{
//    int t = (x % N + N) % N;
//    for (int i = h[t]; i != -1; i = ne[i])
//        if (e[i] == x) return true;
//
//    return false;
//}
//
//int main()
//{
//    cin >> n;
//
//    memset(h, -1, sizeof(h));
//
//    while (n--)
//    {
//        string op;
//        int x;
//        cin >> op >> x;
//
//        if (op == "I") insert(x);
//        else
//            if (query(x)) cout << "Yes" << endl;
//            else cout << "No" << endl;
//    }
//
//    return 0;
//}
//
// 
// 
// 

//#include <iostream>
//using namespace std;
//
//const int N = 100010, M = N * 31;
//int son[M][2], idx, a[N], n;
//
//void insert(int x)
//{
//    int q = 0;
//    for (int i = 30; i >= 0; i--)
//    {
//        int u = x >> i & 1;
//        if (!son[q][u]) son[q][u] = ++idx;
//        q = son[q][u];
//    }
//}
//
//int query(int x)
//{
//    int q = 0, res = 0;
//    for (int i = 30; i >= 0; i--)
//    {
//        int u = x >> i & 1;
//        if (son[q][!u])
//        {
//            res = res * 2 + !u;
//            q = son[q][!u];
//        }
//        else
//        {
//            res = res * 2 + u;
//            q = son[q][u];
//        }
//    }
//
//    return res;
//}
//
//int main()
//{
//    cin >> n;
//    for (int i = 0; i < n; i++) cin >> a[i];
//
//    int res = 0;
//    for (int i = 0; i < n; i++)
//    {
//        insert(a[i]);
//        int t = query(a[i]);
//        res = max(res, t ^ a[i]);
//    }
//
//    cout << res << endl;
//
//    return 0;
//}
//
// 
// 
// 
// 
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int n, m;
//int p[N], _size[N];
//
//int find(int x)
//{
//    if (p[x] != x) p[x] = find(p[x]);
//    return p[x];
//}
//
//int main()
//{
//    cin >> n >> m;
//
//    for (int i = 1; i <= n; i++)
//    {
//        p[i] = i;
//        _size[i] = 1;
//    }
//
//    while (m--)
//    {
//        string op;
//        int a, b;
//        cin >> op;
//
//        if (op == "C")
//        {
//            cin >> a >> b;
//            if (find(a) == find(b)) continue;
//            _size[find(b)] += _size[find(a)];
//            p[find(a)] = find(b);
//        }
//        else if (op == "Q1")
//        {
//            cin >> a >> b;
//            if (find(a) == find(b)) cout << "Yes" << endl;
//            else cout << "No" << endl;
//        }
//        else
//        {
//            cin >> a;
//            cout << _size[find(a)] << endl;
//        }
//    }
//
//    return 0;
//}

//
//#include <iostream>
//using namespace std;
//
//const int N = 50010;
//int p[N], d[N], n, k;
//
//int find(int x)
//{
//    if (p[x] != x)
//    {
//        int t = find(p[x]);
//        d[x] += d[p[x]];
//        p[x] = t;
//    }
//
//    return p[x];
//}
//
//int main()
//{
//    cin >> n >> k;
//
//    for (int i = 1; i <= n; i++) p[i] = i;
//
//    int res = 0;
//    while (k--)
//    {
//        int t, x, y;
//        cin >> t >> x >> y;
//        if (x > n || y > n) res++;
//        else
//        {
//            int px = find(x), py = find(y);
//            if (t == 1)
//            {
//                if (px == py && (d[x] - d[y]) % 3) res++;
//                else if (px != py)
//                {
//                    p[px] = py;
//                    d[px] = d[y] - d[x];
//                }
//            }
//            else
//            {
//                if (px == py && (d[x] - 1 - d[y]) % 3) res++;
//                else if (px != py)
//                {
//                    p[px] = py;
//                    d[px] = d[y] + 1 - d[x];
//                }
//            }
//        }
//    }
//
//    cout << res << endl;
//
//    return 0;
//}

//
//#include <iostream>
//#include <algorithm>
//using namespace std;
//
//const int N = 100010;
//int h[N], ph[N], hp[N], n, _size, m;
//
//void heap_swap(int a, int b)
//{
//    swap(ph[hp[a]], ph[hp[b]]);
//    swap(hp[a], hp[b]);
//    swap(h[a], h[b]);
//}
//
//void down(int u)
//{
//    int t = u;
//    if (u * 2 <= _size && h[u * 2] < h[t]) t = u * 2;
//    if (u * 2 + 1 <= _size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
//    if (u != t)
//    {
//        heap_swap(t, u);
//        down(t);
//    }
//}
//
//void up(int u)
//{
//    while (u / 2 && h[u / 2] > h[u])
//    {
//        heap_swap(u / 2, u);
//        u /= 2;
//    }
//}
//
//int main()
//{
//    cin >> n;
//    while (n--)
//    {
//        int k, x;
//        string op;
//        cin >> op;
//
//        if (op == "I")
//        {
//            cin >> x;
//            ++_size;
//            ++m;
//            ph[m] = _size;
//            hp[_size] = m;
//            h[_size] = x;
//            up(_size);
//        }
//        else if (op == "PM") cout << h[1] << endl;
//        else if (op == "DM")
//        {
//            heap_swap(1, _size);
//            _size--;
//            down(1);
//        }
//        else if (op == "D")
//        {
//            cin >> k;
//            int t = ph[k];
//            heap_swap(t, _size);
//            _size--;
//            up(t), down(t);
//        }
//        else
//        {
//            cin >> k >> x;
//            int t = ph[k];
//            h[t] = x;
//            up(t), down(t);
//        }
//    }
//
//    return 0;
//}

